package contest.sweek199;

/**
 * 1531. 压缩字符串 II
 * AC失败
 * @author code_yc
 * @version 1.0
 * @date 2020/7/26 8:22
 */
public class Solution4 {

    public int getLengthOfOptimalCompression(String s, int k) {
        int n = s.length();
        // 四个维度状态分别表示：当前正在处理的下标，之前一直在处理的字符，之前一直在处理的字符的累积长度，可删除数量
        Integer[][][][] dp = new Integer[n + 1][26][n + 1][k + 1];
        return dfs(dp, s, 0, s.charAt(0), 0, k); // 初始状态的c选择任意即可(这里我设置为第一个下标元素)，num设置为0
    }

    private int dfs(Integer[][][][] dp, String s, int cur, char c, int num, int k) {
        int n = s.length();
        if (cur >= n) {
            return num <= 1 ? num : 1 + (num >= 10 ? 2 : 1);
        }
        if (dp[cur][c - 'a'][num][k] != null) {
            return dp[cur][c - 'a'][num][k];
        }
        // 处理不删的情况
        // 1. 当前处理的下标元素和之前一直在处理的字符不相等
        if (s.charAt(cur) != c) {
            dp[cur][c - 'a'][num][k] = (num <= 1 ? num : 1 + (num >= 10 ? 2 : 1)) + dfs(dp, s, cur + 1, s.charAt(cur), 1, k); // 之前一直处理的字符进行“结账” + 处理后面的字符所需要的最小长度
        } else {
            // 2. 当前处理的下标元素和之前一直在处理的字符相等
            dp[cur][c - 'a'][num][k] = dfs(dp, s, cur + 1, c, num + 1, k);
        }

        // 处理删除的情况
        if (k > 0) {
            dp[cur][c - 'a'][num][k] = Math.min(dp[cur][c - 'a'][num][k], dfs(dp, s, cur + 1, c, num, k - 1));
        }
        return dp[cur][c - 'a'][num][k];
    }
}
